作者:ccer | 来源:互联网 | 2023-06-30 12:59
Sagemath | 基于大整数分解的Rabin加密
问题概述
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/d3a6fd2b8c629ed4.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NDU1Mw==,size_16,color_FFFFFF,t_70#pic_center)
分析
使用sagemeth进行破解运算,运算过程大约15秒。
首先将N质因数分解成两个素数p,q:
p=990932843298892349238943242791,
q=2387883598789374983927498237627。
再用模幂计算出:
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/f78869cb5c1e9ccd.png#pic_center)
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/8d39d2f08ef3facb.png#pic_center)
可得:
mp=358546986862207226911256688941,
mq=1790411145826943505290886300376;
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/bce4b74554a993bd.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NDU1Mw==,size_16,color_FFFFFF,t_70#pic_center)
欧几里得辗转相除法求出满足sp + tq=1的s、t的值:
s=417850213941792666727100662729;
t=-173401040479659357453257331194。
再用中国剩余定理解得x1,x2,x3,x4:
X1=1180750646513203924856355379026414770979645149607;
X2=2366232284013966098921140426254459982575397735186553227547350
X3=874422063025296895941599983057263334241694752879172800315388
X4=1491810220989849953626053647122053003712729397078360072381569。
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/86b89b73efb309d2.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NDU1Mw==,size_16,color_FFFFFF,t_70#pic_center)
猜想将其转换成16进制看一下是否有进一步的含义,x1,x2,x3,x4转换后的结果如图:
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/de28907d04e7a3a9.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NDU1Mw==,size_16,color_FFFFFF,t_70#pic_center)
进一步4个一组,查询编码,看看是否有对应的意义,x1所对应的汉字如下,x2、x3、x4无对应含义:
![在这里插入图片描述](https://img8.php1.cn/3cdc5/1307a/807/278596058cf0b1e6.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg5NDU1Mw==,size_16,color_FFFFFF,t_70#pic_center)